1. Field of the Invention
The present invention relates to a method for Internet Protocol address lookups with efficient use of memory, more particularly, to a method for speeding up Internet Protocol address lookups by constructing Prefix Information Tables to represent the information on the routing table in the router.
2. Background of the Invention
The speed of conventional Internet Protocol (IP) lookup in the routers has become unsatisfactory owing to the dramatically increased traffic flow in the Internet, and comparable bandwidths needed. To find the output port for a destination address indicated by a packet sent in a router, the Internet router has to look up for the longest matching prefix, which is called Best Matching Prefix (BMP), for the destination address. But in prior art, the Internet Protocol lookup schemes are complicated and need lots of time to locate the BMP, and thus form a bottleneck on the Internet. In the present invention, a brand new scheme for IP lookups is introduced, which is capable of enhancing the speed of the IP lookups efficiently. The main concept behind the scheme is grounded upon two Prefix Information Tables (PITs), which are respectively the PIT at level m, and the PIT at level n. The two PITs partition the conventional binary tree expanded by the routing table into segments. Next comes with a matching process for the IP address needed to be routed by the router in the PIT at level m or/and the PIT at level n to find the segment the IP address locates on the binary tree. Once the segment on the binary tree is decided, either the output port for the destination address is found or the Lookup Table is addressed. In the Lookup Table addressed, a matching process for the destination address is to be conducted to locate the BMP, and thus the output port is known through the Lookup Table.
In this invention, there needs only 1 hash plus 2 memory accesses for the worst cases. In an IPv4 backbone router with 41,000 routing entries, there needs, on an average, 0.53 hashes plus 1.4 memory accesses. With the use of 50 ns SDRAM, the scheme offers a lookup speed up to 10 millions packets per second. Furthermore, the lookup speed can be improved linearly with the speedup of the memory used. Additionally, the update to the routing table is easy and is low on the overhead and the memory needed for the forwarding table is only about 0.6 MBytes. The scheme and the advantages the scheme offers mentioned above can efficiently settle the problems occurred in prior art on the IP lookup issue.
The Internet Protocol (IP) address lookup scheme in the most primitive work is to put prefixes on a router into hash tables, respectively, based on their lengths. When a packet is sent into the router, a hash process is launched through the prefix hash tables. The hash process goes through from the longest to the shortest prefix hash table. The IP lookup scheme is based on the conventional Trie for the Best Matching Prefix (BMP), which is shown in FIG. 1. In the worse cases, 32 hashes are needed for the IP lookup; in the average cases, over 10 hashes are needed. The speed this scheme performs apparently cannot meet the requirements for the future high-speed routers.
The first prior art in this section is suggested by M. Waldvogel, G. Varghese, J. Turner and B. Plattner, entitled xe2x80x9cScalable High Speed IP Routing Lookupsxe2x80x9d, for IP routing lookups. Compared with the traditional IP lookup based on a Trie, the solution organizes the prefix IP addresses according to their lengths into hash tables (one hash table for each prefix length). Binary search is then used over the hash tables (instead of the routing entries themselves) for the BMP, which is shown in FIG. 2. Coupled with some optimizations, such as Mutating Binary Search, which exploits the traffic characteristics of the Internet, used to further reduce the complexity, the access times of memory, the speed of IP lookups can be further improved.
The binary search is started with putting xe2x80x9cmarkersxe2x80x9d into the hash tables at each level. Alternatively, each prefix P of length L has to place markers at all levels shorter than L. The markers indicate that there exist the prefixes of greater lengths in the subtree spanning from the node itself. The scheme starts the hash search at the median length of the Trie and progresses using binary search. If there is a match, all lengths greater than the median (the lower half of the Trie) are searched recursively; otherwise, all lengths less than the median (the upper half of the Trie) are searched instead. Additionally, Mutating Binary Search can be adopted to reduce the time of searching for the BMP; namely, whenever an entry is accessed, the searching proceeds with the subtree expanded from the entry.
In the algorithm, the size of the forwarding table is independent on the time for IP lookups, and the memory access time is in 2-based logarithm relationship with the length of the IP address, and which is advantageous to support for the future IPv6. In this scheme, an average numbers hash processes is 2, and log2 (the bit number of the IP address) for the worst cases. Since the length of the IP address is 32 bits in the IPv4 backbone, 5 hashes are needed for the worse cases. The approach has the advantages of being scalable (for future IPv6) and reduced IP lookup time. However, the data structures used are complicated and the update of an entry in the routing table might result in a large number of the entries being updates in the lookup table as the markers need to be reentered in tables at every level of the Trie. So making the lookup table update has to rebuild the tree periodically.
Gupta, Lin, and McKeown presented a fast IP routing lookup scheme in the hope of achieving a speed up to a gigabit per second by means of Longest Prefix Matching in hardware process, which is referred to as the second prior art in this section. In the scheme, IP addresses each are divided into two sections, the first 24 bits and the last 8 bits. A table TBL24 is created to accommodate the prefixes with lengths less than or equal to 24 bits. If the first bit is 0, then the other 15 bits is used to indicate the next hop. On the contrary, the first bit is 1, then the other 15 bits stands for a pointer which points to TBLlong, which is created to accommodate the prefixes which are longer than 24 bits. The implemented hardware for the lookup scheme is shown in FIG. 3.
In accordance with this scheme, an average time of 1 (in fact, a little more than 1) memory access is needed, and the maximum number of 2 memory accesses are needed. Although the IP lookups scheme is very efficient in speed, it may call for 33MB DRAM to store data structures needed. The use of memory is instead very inefficient. The scheme is not able to support efficiently the future Internet Protocol scheme, which have address fields of 128 bits. Furthermore, a distributed database management is hard to implemented based on this scheme.
The present invention is aimed to provide a method for speeding up Internet Protocol (IP) address lookups with efficient use of memory. The lookup process may include the characteristics as follows. First, the lesser time of accessing memory for IP lookups the better. Second, for the worst case, the time of accessing memory must be limited in a range in order to attain the IP lookup speed. Third, in accessing memory, it is preferred to execute with pipelined operation. Last, it is desired to have a smaller size of memory required for data structures. Additionally, it will be better if the data structures used are more concise and compact.
According to one aspect of the present invention, a method for speeding up Internet Protocol address lookups with efficient use of memory is disclosed. The method includes the following steps: First, establishing a Prefix Information Table (PIT), PIT-m, corresponding to a subtree expanding from a node on m-th level on the Trie, and a PIT, PIT-n, corresponding to a subtree expanding from a node on n-th level on the Trie for partitioning the Trie into several segments to map into all IP addresses. Then looking up the Best Matching Prefix (BMP) for the Internet Protocol address through the PIT-m and the PIT-n for finding an output port or for finding the Lookup Table (LT) corresponding to the IP address. Finally, checking up the LT for finding a BMP, and thus an exact output port is obtained. The PIT-m format comprises: an m-bit entry number identification, a 1-bit direction identification, a 1-bit prefix identification, and a 14-bit pointer; and the PIT-n comprises: n-bit entry number identification, 1-bit direction identification, a 1-bit prefix identification, and 14-bit pointer. While in Lookup Tables, there store output ports corresponding to prefix entries. By use of a fraction of an IP address as an index into the Lookup Table, an exact output port can be found.